package 算法很美.唯一只出现一次的数字;

import java.util.Scanner;

/**
 * @ClassName : 找出数组中只出现一次的数字
 * @Author : 骆发茂
 * @Date: 2021/3/1 15:15
 * @Description :找出数组中只出现一次的数字，其它数字都出现了两次
 */
/*题目：一个整型数组里除了一个数字之外，其它的数字都出现了两次。请写程序找出这个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：由于题目要求时间复杂度为O(n)，所以先排序然后比较相邻数字是否相同的思路被排除。

            空间复杂度是O(1)，辅助空间被限制，所以hash表的思路也被排除。

           那么这个题的突破口在哪里呢？注意这个数组的特殊性：其它数字都出现了两次，只有一个数出现了一次。可以想到运用异或运算，任何一个数字异或它自己都等于0。

           如果我们从头到尾依次异或数组中的每一个数，那么最终的结果就是那个只出现一次的数字，因为其他出现两次的数字全部在异或中被抵消为0了（异或运算遵循交换分配率）。

           举个栗子：2  3  4  2  3

           所有数字依次异或运算：2 xor 3 xor 4 xor 2 xor 3 = (2 xor 2) xor (3 xor 3) xor 4= 0 xor 0 xor 4 = 4

          最终结果4就是我们要找的那个只出现一次的数字。*/
public class 方法1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一组整数，以英文逗号分隔：");
        String str = sc.nextLine();
        //   str = str.substring(1, str.length()-1);//去掉键盘输入的字符串中的"["和"]",如果有的话
        String[] s = str.split(",");//将字符串以","分割，转为一个字符串数组
        int[] arr = new int[s.length];//定义一个整形数组，准备用来存数据了
        for (int i = 0; i < arr.length; i++)
            arr[i] = Integer.parseInt(s[i]);//将字符串转为int类型数据存入整型数组中
        /*注：这里直接将字符串转为整型数据使用的是包装类Integer类的parseInt()静态方法，
        调用时直接类名调用，方法返回值为Integer类型，
        但是可以自动拆箱为int型，因此用int或Integer类型接收均可。*/
        System.out.println("=========打印arr[]数组内容=============");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
        System.out.println("");
        System.out.println("==========唯一只出现一次的数字为：==========================");
        Find_Num(arr);//调方法
    }



    public static void Find_Num(int[] arr) {
        if (arr.length < 2) {
            System.out.println("rr.length < 2,error");
        } else {
            int result = 0;
            for (int i = 0; i < arr.length; i++) {
                result ^= arr[i];
            }
            if (result == 0) {
                System.out.println("没有唯一只出现一次的数字，输入错误");
            }
            else {
                System.out.println(result);
            }

        }
    }
}

